COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a22.tex[106,phy] \today\hfill}

\bigskip
\ctrline{{\bf Sliding Blocks} (Mazlak)}

\bigskip
The puzzle below contains eight sliding blocks, numbered 1 to~8, in a box.
The problem is to slide the blocks around until the second position is
reached.
$$\vbox{\offinterlineskip
\halign{\strut#&\vrule#&\quad\hfil#\hfil\quad&\vrule#&\quad\hfil#\hfil\quad%
&\vrule#&\quad\hfil#\hfil\quad&\vrule#\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&8&&7&&6&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&5&&4&&3&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&2&&1&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
}}
\qquad\qquad
\vbox{\offinterlineskip
\halign{\strut#&\vrule#&\quad\hfil#\hfil\quad&\vrule#&\quad\hfil#\hfil\quad%
&\vrule#&\quad\hfil#\hfil\quad&\vrule#\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&1&&2&&3&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&4&&5&&6&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
&&7&&8&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&\cr
\multispan7\hrulefill\cr
}}$$

According to Martin Gardner ({\sl Scientific American\/}, March 1965, 
pg.~282), no human had ever found a solution in less than 36~moves,
but a computer found ten 30-move solutions.
Write a program to find them.

\bigskip
\item{} Hint: Represent the positions above by the strings
9876543210 and 912356780; the first digit shows where the zero
is and the zero represents the empty space. Generate all positions
you can get to from each of the above in 15~turns, and look for
positions common to the two sets. Eliminate sequences that repeat
earlier positions.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984


\bye